/*
https://leetcode.cn/problems/check-if-there-is-a-valid-path-in-a-grid/solutions/164369/jiang-dao-lu-gui-fan-hua-zhuan-huan-wei-01shu-zu-b/

*/

class Solution {
public:
    // 定义四个方向：右、左、下、上
    vector<pair<int, int>> dir{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 如果网格只包含一个单元格，则直接返回 true
        if (m == 1 && n == 1) {
            return true;
        }
        
        // 扩展后的网格大小
        int mm = 3 * m, nn = 3 * n;
        
        // 创建扩展后的网格 matrix
        vector<vector<int>> matrix(3 * m, vector<int>(3 * n, 0));
        
        // 根据 grid 填充 matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {  // 右
                    for (int t = 0; t <= 2; t++) {
                        matrix[3 * i + 1][3 * j + t] = 1;
                    }
                } else if (grid[i][j] == 2) {  // 下
                    for (int t = 0; t <= 2; t++) {
                        matrix[3 * i + t][3 * j + 1] = 1;
                    }
                } else if (grid[i][j] == 3) {  // 右下
                    matrix[3 * i + 1][3 * j] = 1;
                    matrix[3 * i + 1][3 * j + 1] = 1;
                    matrix[3 * i + 2][3 * j + 1] = 1;
                } else if (grid[i][j] == 4) {  // 左下
                    matrix[3 * i + 1][3 * j + 1] = 1;
                    matrix[3 * i + 1][3 * j + 2] = 1;
                    matrix[3 * i + 2][3 * j + 1] = 1;
                } else if (grid[i][j] == 5) {  // 上右
                    matrix[3 * i][3 * j + 1] = 1;
                    matrix[3 * i + 1][3 * j + 1] = 1;
                    matrix[3 * i + 1][3 * j] = 1;
                } else if (grid[i][j] == 6) {  // 上左
                    matrix[3 * i + 1][3 * j + 1] = 1;
                    matrix[3 * i][3 * j + 1] = 1;
                    matrix[3 * i + 1][3 * j + 2] = 1;
                }
            }
        }

        // 使用队列进行 BFS
        queue<pair<int, int>> Q;
        vector<vector<bool>> visit(3 * m, vector<bool>(3 * n, false));

        // 初始化队列和访问标记
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (matrix[i][j]) {
                    Q.push({i, j});
                    visit[i][j] = true;
                }
            }
        }

        // 开始 BFS
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();

            for (auto d : dir) {
                int x = p.first + d.first;
                int y = p.second + d.second;

                // 检查边界条件和是否已经访问过
                if (x >= 0 && x < mm && y >= 0 && y < nn && !visit[x][y] && matrix[x][y]) {
                    visit[x][y] = true;
                    Q.push({x, y});

                    // 如果到达了右下角的 3x3 子网格中的任意一点，说明找到了有效路径
                    if (x / 3 == m - 1 && y / 3 == n - 1) {
                        return true;
                    }
                }
            }
        }

        // 如果没有找到有效路径，返回 false
        return false;
    }
};

